Digital signature schemes that are a type of public-key encryption are technology used for identifying a sender and preventing data falsification when data is sent from a receiving apparatus to a transmitting apparatus. To explain the schemes simply, the transmitting apparatus creates signature data for data desired to be transmitted using a private key of the transmitting apparatus, and then transmits the signature data to the receiving apparatus together with the desired data. The receiving apparatus performs a verification of the signature data using a public key corresponding to the private key of the transmitting apparatus to judge whether the desired data has been falsified (see Non-Patent Reference 1, for example). Here, it is difficult to calculate a value of the private key from the public key.
Recently, the NTRU encryption is proposed as a public-key encryption enabling high-speed processing (e.g., Non-Patent Reference 2). The NTRU encryption performs encryption and decryption by polynomial operations that can be implemented at higher speeds, as compared to RSA encryption that carries out module exponentiation under a certain rule and an elliptic curve cryptosystem that performs scalar multiplication for points on an elliptic curve. Hence, the NTRU encryption achieves higher-speed processing than conventional public-key encryption, and is also capable of performing, when used in software processing, the processing in a practical period of time.
Accordingly, an encryption communication system using the NTRU encryption for the public-key encryption has an advantage that processes of the transmitting apparatus and receiving apparatus can be performed at higher speeds than an encryption communication system using conventional public-key encryption.
Although the proposed NTRU encryption scheme mentioned above is confidentiality encryption for encrypting data, later in time a digital signature scheme using the NTRU encryption has been proposed (see Non-Patent Reference 3). As to digital signature schemes, their schemes have been changed several times because of advent of cryptanalysis and the like. The following gives a brief description of a digital signature scheme called NTRUSign (for more details, see Patent Reference 2 and Non-Patent Reference 4).
In the key generation under the NTRUSign signature scheme, the private key and public key are generated by using multiple elements in a polynomial ring R with integer coefficients and an ideal of the ring R module a polynomial X^N−1. Here, “X^a” denotes X to the power of a. For generating a signature under the NTRUSign signature scheme for a message, the generated private key and a 2·N-dimensional vector, which is a hash value of the message, are used. For the signature verification of the NTRUSign signature scheme, the public key, the signature for the message, and the 2·N-dimentional vector are used. Since Non-Patent References 4 and 5 describe a ring and an ideal of the ring used in the NTRUSign signature scheme, their descriptions are left out here.
<NTRUSign Signature Scheme>
(1) Parameters of NTRUSign Signature Scheme
The NTRUSign signature scheme uses parameters of nonnegative integers, N, q, df, dg, and Normbound. The meanings of these parameters are described next.
(1-1) Parameter N
The NTRUSign signature scheme is a digital signature scheme that performs signature generation and verification using polynomial operations. The degree of a polynomial used in the NTRUSign signature scheme is determined by the parameter N.
Polynomials used in the NTRUSign signature scheme are polynomials of degree N−1 or less with integer coefficients for the above parameter N. A polynomial X^4+X^3+1 is an example in the case when N=5. Note that a (mod X^N−1) operation is performed on the polynomial so as to always calculate a polynomial of degree N−1 or less with integer coefficients. This is because, by performing the (mod X^N−1) operation, a relational expression X^N=1 is realized, and therefore a variable of degree N or more can always be converted into a variable of degree N−1 or less. Here, it can be understood that a polynomial with integer coefficients obtained by performing the (mod X^N−1) operation on a polynomial is an element in the polynomial ring R.
In addition, both a public key h and a signature s are expressed as polynomials of degree N−1 or less. Besides, the private key is a set of four polynomials of degree N−1 or less (f, g, F, G). Namely, f, g, F and G are all polynomials of degree N−1 or less and elements of the polynomial ring R. Note that the set of four (f, g, F, G) is further treated as a pair of two pairs (f, g) and (F, G) and hereinafter sometimes denoted as {(f, g), (F, G)}.
Then, the polynomial operation uses the relational expression X^N =1 for the parameter N to produce the result always being a polynomial of degree N−1 or less. For example, in the case where N=5, the product of a polynomial X^4+X^2+1 and a polynomial X^3+X is always a polynomial of degree N−1 or less, as shown below, due to a relationship X^5=1:
                                          (                                          X                ^                4                            +                              X                ^                2                            +              1                        )                    ×                      (                                          X                ^                3                            +              X                        )                          =                              X            ^            7                    +                      2            ·                          X              ^              5                                +                      2            ·                          X              ^              3                                +          X                                        =                                            X              ^              2                        ·            1                    +                      2            ·            1                    +                      2            ·                          X              ^              3                                +          X                                        =                              2            ·                          X              ^              3                                +                      X            ^            2                    +          X          +          2                    where × is the symbol for the multiplication of a polynomial by a polynomial, and # is the symbol for the multiplication of an integer by a polynomial (or an integer by an integer).
Note that, in the NTRUSign signature scheme, a polynomial of degree N−1, a=a—0+a—1*X+a—2*X^2+ . . . +a_(N−1)*X^(N−1) is equated with a vector (a—0, a—1, a—2, . . . a_(N−1)). a—0, a—1, a—2, . . . , and a_(N−1), are coefficients of the polynomial a and integers.
(1-2) Parameter q
The NTRUSign signature scheme uses the parameter q which is an integer of 2 or more and an ideal of the polynomial ring R. Coefficients of polynomials in the NTRUSign signature scheme are remainders modulo q.
(1-3) Parameters df and dg
How to select a polynomial f, which is a part of the private key used in the NTRUSign signature scheme, and a polynomial g used with the polynomial f for generating a polynomial h, which is the public key, is determined by parameters df and dg, respectively.
The polynomial f is selected so that df pieces of coefficients are 1 and the remaining coefficients are 0. That is, the polynomial f is a polynomial of degree N−1 or less, and has N pieces of coefficients from degree 0 (constant term) to degree N−1. Here, the polynomial f must be selected so that, among the N pieces of the coefficients, df pieces of coefficients are 1 and (N-df) pieces of coefficients are 0.
Then, the polynomial g is selected so that dg pieces of coefficients are 1 and the remaining coefficients are 0.
(1-4) Parameter Normbound
In the NTRUSign signature scheme, a distance between a 2·N-dimensional vector created from the signature s and a 2·N-dimensional vector, which is a hash value of the message, to be hereinafter described is calculated, and the authenticity of the signature is judged based on the distance. The Normbound is a threshold used in the judgment. Namely, if the distance is less than the Normbound, the signature is accepted as an authentic signature, whereas if the distance is the same as the Normbound or more, it is denied as an inauthentic signature.
Non-Patent Reference 4 gives an example of parameters of the NTRUSign signature scheme: (N, q, df, dg, Normbound)=(251, 128, 73, 71, 310).
(2) Hash Value of Message and Distance Between Norm and Vector
The NTRUSign signature scheme creates a signature corresponding to a hash value of a message m. The hash value of the message m is a polynomial pair of degree N, (m1, m2), and is equated with a 2·N-dimensional vector. Non-Patent Reference 1 details the hash function that calculates a hash value from a message.
The NTRUSign signature scheme uses a distance of a vector for the signature verification. The following describes the definition.
A norm ∥a∥ of the polynomial a=a—0+a—1·X+a—2·X^2+ . . . +a_(N−1)·X^(N−1) is defined as:∥a∥=sqrt((a—0−μ)^2+(a—1−μ)^2+ . . . +(a_(N−1)−μ)^2),μ=(1/N)·(a—0+a—1+a—2+ . . . +a_(N−1)),
where sqrt(x) is a square root of x.
The norm ∥(a, b)∥ of the pair (a, b) of the polynomials a and b is defined as:∥(a,b)∥=sqrt(∥a∥^2+∥b∥^2).
The distance between the pair (a, b) of the polynomials a and b and the pair (c, d) of the polynomials c and d is defined as ∥(c-a, d-b)∥.
Herewith, a polynomial of degree N−1 or less with integer coefficients obtained by performing the (mod X^N−1) operation can be regarded as an N-dimensional array in which the addition, subtraction, multiplication and a norm indicating the size of an element are defined, and the polynomial ring R can be regarded as a set of N-dimensional arrays.
(3) Key Generation of NTRUSign Signature Scheme
The NTRUSign signature scheme randomly generates the polynomials f and g using the parameters df and dg, as mentioned above. Then, as Non-Patent Reference 4 describes, a polynomial Fq which satisfies Fq×f=1(mod q) is used in an equation,h=Fq×g(mod q)to thereby generate the polynomial h. Here, the polynomial Fq is referred to as an inverse element of the polynomial f. Furthermore, the polynomials F and G are obtained, the norm of which is small enough to satisfy the following equation:f×G−g×F=q. 
The private key is denoted as {(f, g), (F, G)}, and the public key, as h. The private key is a key for generating a signature and also called a signature generation key. Additionally, the public key is a key for verifying the signature and also called a signature verification key.
Here, x=y(mod q) is an operation to assign, to a coefficient of degree i of a polynomial x, a reminder obtained when a coefficient of degree i of a polynomial y is divided by a modulus q in a manner that the remainder falls in the range from 0 to q−1 (0≦i≦N−1). That is, it is an operation where a mod-q operation is performed on a polynomial y so as to keep each coefficient of the polynomial y within the range of 0 and (q−1), to whereby obtain a polynomial, which is then assigned to the polynomial x.
(4) Signature Generation of NTRUSign Signature Scheme
In the signature generation under the NTRUSign signature scheme, the signature s of the message m, on which digital signature operation is performed, is calculated. First, the 2·N-dimensional vector (m1, m2) (m1 and m2 are polynomials of degree N), which is a hash value for the message m, is calculated.
The 2·N-dimensional vector (m1, m2) and private key {(f, g), (F, G)} are used to calculate the polynomials a, b, A and B satisfying the following equations:G×m1−F×m2=A+q×B; and−g×m1+f×m2=a+q×b. 
Here, coefficients of A and a are remainders obtained when G×m1−F×m2 is divided by the modulus q in a manner that the remainders fall in the range from <−q/2>+1 to <q/2>. That is, in the case where each remainder obtained by the division by the modulus q is between <q/2> and q−1, q is subtracted from the remainder so that the remainder is adjusted to fall in the above range. Here <x>denotes the largest number among numbers being x or less. For example, <−½>=−1.
Next, s and t are calculated using the following equations, and s is output as a signature:s=f×B+F×b(mod q); andt=g×B+G×b(mod q).
(5) Signature Verification of NTRUSign Signature Scheme
In the signature verification under the NTRUSign signature scheme, it is verified whether the signature s is an authentic signature of the message m, on which digital signature operation is performed. First, the 2·N-dimensional vector (m1, m2), which is a hash value for the message m, is calculated.
The polynomial t is calculated with the following equation using the public key h:t=s×h(mod q).The distance between the 2·N-dimensional vectors (s, t) and (m1, m2) is found, and the distance is then checked whether to be less than the Normbound. When it is less than the Normbound, the signature s is accepted, being determined as the authentic signature. On the other hand, if the distance is the same as the Normbound or more, it is denied, being determined as an inauthentic signature.
<Patent Reference 1> Published Japanese Translation of a PCT Application Originally Filed in English, No. 2000-516733.
<Patent Reference 2> W02003/050998
<Non-Patent Reference 1> Tatsuaki Okamoto and Hiroshi Yamamoto, “Modern Cryptography”, Sangyo Tosho (1997).
<Non-Patent Reference 2> J. Hoffstein, J. Pipher and J. H. Silverman, “NTRU: A Ring-Based Public Key Cryptosystem”, Lecture Notes in Computer Science 1423, pp. 267-288, Springer-Verlag, (1998).
<Non-Patent Reference 3>J. Hoffstein, J. Pipher and J. Silverman, “NSS: An NTRU Lattice-Based Signature Scheme”, Advances in Cryptology-Eurocrypt '01, LNCS, Vol. 2045, pp. 123-137, Springer-Verlag, (2001).
<Non-Patent Reference 4> J. Hoffstein, N. Graham, J. Pipher, J. Silverman and W. Whyte, “NTRUSign: Digital Signatures Using the NTRU Lattice”, CT-RSA '03, LNCS, Vol. 2612, pp. 122-140, Springer-Verlag, (2003).
<Non-Patent Reference 5>J. Hoffstein, N. Graham, J. Pipher, J. H. Silverman and W. Whyte, “NTRUSign: Digital Signatures Using the NTRU Lattice Preliminary Draft 2—Apr. 2, 2002”, <http://www.ntru.com/cryptolab/pdd/NTRUSign-preV2.pdf> (Accessed Jan. 20, 2005).